package com.leetcode.algorithm.y19.m03;

import com.leetcode.algorithm.common.ListNode;
import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (done)669. 修剪二叉搜索树
 * (done)108. 将有序数组转换为二叉搜索树
 * (done)109. 有序链表转换二叉搜索树
 * 
 * @author: jie.deng
 * @time: 2019年3月7日 下午5:01:45
 */
public class MySolution0307 {

	/**
	 * 669. 修剪二叉搜索树
	 * 
	 * 给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
	 * 
	 * 示例 1:
	 * 
	 * 输入: 
	 *     1
	 *    / \
	 *   0   2
	 * 
	 *   L = 1
	 *   R = 2
	 * 
	 * 输出: 
	 *     1
	 *       \
	 *        2
	 * 示例 2:
	 * 
	 * 输入: 
	 *     3
	 *    / \
	 *   0   4
	 *    \
	 *     2
	 *    /
	 *   1
	 * 
	 *   L = 1
	 *   R = 3
	 * 
	 * 输出: 
	 *       3
	 *      / 
	 *    2   
	 *   /
	 *  1
	 * 
	 * @param root
	 * @param L
	 * @param R
	 * @return
	 */
	public TreeNode trimBST(TreeNode root, int L, int R) {
		if (root == null) {
			return null;
		}
		TreeNode cur = root;
		if (cur.val < L) {
			return trimBST(cur.right, L, R);
		} else if (cur.val > R) {
			return trimBST(cur.left, L, R);
		} else {
			cur.left = trimBST(cur.left, L, R);
			cur.right = trimBST(cur.right, L, R);
		}
		return cur;
	}

	/**
	 * 108. 将有序数组转换为二叉搜索树
	 * 
	 * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
	 * 
	 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
	 * 
	 * 示例:
	 * 
	 * 给定有序数组: [-10,-3,0,5,9],
	 * 
	 * 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
	 * 
	 *       0
	 *      / \
	 *    -3   9
	 *    /   /
	 *  -10  5
	 * 
	 * @param nums
	 * @return
	 */
	public TreeNode sortedArrayToBST(int[] nums) {
		return sortedArrayToBST(nums, 0, nums.length);
	}

	private TreeNode sortedArrayToBST(int[] nums, int fromIdx, int toIdx) {
		if (fromIdx >= toIdx) {
			return null;
		}
		int mid = (fromIdx + toIdx - 1) / 2;
		TreeNode root = new TreeNode(nums[mid]);
		root.left = sortedArrayToBST(nums, fromIdx, mid);
		root.right = sortedArrayToBST(nums, mid + 1, toIdx);
		return root;
	}

	public TreeNode sortedArrayToBST2(int[] nums) {
		TreeNode root = null;
		for (int num : nums) {
			root = insert(num, root);
		}
		return root;
	}

	private TreeNode insert(int num, TreeNode t) {
		if (t == null) {
			return new TreeNode(num);
		}
		if (num < t.val) {
			t.left = insert(num, t.left);
		} else if (num > t.val) {
			t.right = insert(num, t.right);
		}
		return balance(t);
	}

	private TreeNode balance(TreeNode t) {
		if (t == null) {
			return t;
		}
		if (height(t.left) - height(t.right) > 1) {
			if (height(t.left.left) >= height(t.left.right)) {
				// LL型
				t = rotateWithLeftChild(t);
			} else {
				// LR型
				t = doubleWithLeftChild(t);
			}
		} else if (height(t.right) - height(t.left) > 1) {
			if (height(t.right.right) >= height(t.right.left)) {
				// RR型
				t = rotateWithRightChild(t);
			} else {
				// RL型
				t = doubleWithRightChild(t);
			}
		}
		return t;
	}

	private int height(TreeNode t) {
		if (t == null) {
			return -1;
		}
		return Math.max(height(t.left), height(t.right)) + 1;
	}

	// LL型一次右旋
	public TreeNode rotateWithLeftChild(TreeNode t) {
		TreeNode left = t.left;
		t.left = left.right;
		left.right = t;
		return left;
	}

	// LR型 先一次左旋然后一次右旋
	public TreeNode doubleWithLeftChild(TreeNode t) {
		t.left = rotateWithRightChild(t.left);
		return rotateWithLeftChild(t);
	}

	// RR型一次左旋
	public TreeNode rotateWithRightChild(TreeNode t) {
		TreeNode right = t.right;
		t.right = right.left;
		right.left = t;
		return right;
	}

	// RL型 先一次右旋然后一次左旋
	public TreeNode doubleWithRightChild(TreeNode t) {
		t.right = rotateWithLeftChild(t.right);
		return rotateWithRightChild(t);
	}
	
	/**
	 * 109. 有序链表转换二叉搜索树
	 * 
	 * 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
	 * 
	 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
	 * 
	 * 示例:
	 * 
	 * 给定的有序链表： [-10, -3, 0, 5, 9],
	 * 
	 * 一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
	 * 
	 *       0
	 *      / \
	 *    -3   9
	 *    /   /
	 *  -10  5
	 * 
	 * @param head
	 * @return
	 */
	public TreeNode sortedListToBST(ListNode head) {
		TreeNode root = null;
		while (head != null) {
			root = insert(head.val, root);
			head = head.next;
		}
		return root;
	}

}
